package solution;

import solution.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * <a href="">
 * WC7 求二叉树的前序遍历</a>
 *
 * @author or2
 * @Description 求给定的二叉树的前序遍历。
 * 备注；用递归来解这道题很简单，你可以给出迭代的解法么？
 * @create 2021年09月14日 时间: 19:35
 */
public class PreorderTraversal {
    /**
     * @param root TreeNode类
     * @return int整型ArrayList
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            ans.add(pop.val);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }

        return ans;
    }
}
